/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package kotionokyurievna.gmail.com.mergesort.logic;

/**
 *
 * @author Kateryna_Reznik
 */
public class MergeSorter implements Runnable{
    private int arrayToSort[];
    private Thread t;
    
    public MergeSorter( int array[]){
        int length = array.length;
        this.arrayToSort = new int[ length ];
        System.arraycopy(array, 0, arrayToSort, 0, length);
    }
    
    @Override
    public void run() {
        mergeSort(arrayToSort);
    }
    
    
    public void mergeSort(int[] array) {
        if (array.length > 1) {
            // split array into two halves
            int[] left = leftHalf(array);
            int[] right = rightHalf(array);
            
            // recursively sort the two halves
           
           
            t = new Thread ( new MergeSorter( left ));
            t.start();
            mergeSort(right);
             
            try{
                t.join();               
                // merge the sorted halves into a sorted whole
                merge(array, left, right);
            }
            catch( InterruptedException ex ){
                
            }
        }
    }
    
    // Returns the first half of the given array.
    public int[] leftHalf(int[] array) {
        int size1 = array.length / 2;
        int[] left = new int[size1];
        for (int i = 0; i < size1; i++) {
            left[i] = array[i];
        }
        return left;
    }
    
    // Returns the second half of the given array.
    public int[] rightHalf(int[] array) {
        int size1 = array.length / 2;
        int size2 = array.length - size1;
        int[] right = new int[size2];
        for (int i = 0; i < size2; i++) {
            right[i] = array[i + size1];
        }
        return right;
    }
    
    // Merges the given left and right arrays into the given 
    // result array.  Second, working version.
    // pre : result is empty; left/right are sorted
    // post: result contains result of merging sorted lists;
    public void merge(int[] result, int[] left, int[] right) {
        int i1 = 0;   // index into left array
        int i2 = 0;   // index into right array
        
        for (int i = 0; i < result.length; i++) {
            if ( (i2 < right.length) && (i1 < left.length )) {
                if ( left[i1] <= right[i2] ){
                    result[i] = left[i1];    // take from left
                    i1++;
                }
                else{
                    result[i] = right[i2];    
                    i2++;
                }
            } else {
                if ( i1 >= left.length ){ 
                    result[i] = right[i2];   // take from right
                    i2++;
                }
                else{
                    result[i] = left[i1];   // take from right
                    i1++;
                }
            }
        }
    }
    
    public int[] getArray(){
        return arrayToSort;
    }
}
